package code1_100.code1_10;

import javax.management.remote.JMXAddressable;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 * 输入: s = ""
 * 输出: 0
 */
public class _3lengthOfLongestSubstring {

    /**
     * 思考：第一下想到的就是传说中的KMP算法（但算法具体思想已经忘记，先用暴力解决一遍）
     * 结果：本来以为只有26个字母，写完才发现由英文字母，数字，符号，空格组成
     *
     * 执行用时：     * 13 ms     * , 在所有 Java 提交中击败了     * 19.11%    * 的用户
     * 内存消耗：     * 38.7 MB     * , 在所有 Java 提交中击败了     * 22.78%     * 的用户
     *
     * 终于他娘的用暴力解决了！这题气死我了！
     *
     * 总结：此类的统一可以用滑动窗口思想，滑动窗口的进一步优化是，对一进一出的两个字符进行比较，相等则下一个，不相等则进行判定
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if(s.length()==1)return 1;
        if(s.length()==0)return 0;
        int[] arr;
        char temp = ' ';
        int maxAns = 0;
        int max;
        for (int i = 0; i < s.length(); i++) {
            max = 0;
            arr = new int[95];
            for (int j = i; j < s.length(); j++) {
                temp = s.charAt(j);
                if(arr[temp-32]==0){
                    arr[temp-32]=1;
                    max++;
                    maxAns = Math.max(max,maxAns);
                }else {
                    break;
                }
            }
        }
        return maxAns;
    }

    /**
     * 题解方法：此方法和我的方法一模一样，但人家优化的好，效率比我高。我维护的是95宽度的数组，题解用的可变数组
     * 注：题解也只给了一种方法，只有一种方法
     *
     * 执行用时：     * 6 ms     * , 在所有 Java 提交中击败了     * 71.32%     * 的用户
     * 内存消耗：     * 38.1 MB     * , 在所有 Java 提交中击败了     * 95.88%     * 的用户
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring1(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("au"));
    }
}
